package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href='https://leetcode.cn/problems/balance-a-binary-search-tree/'>将二叉搜索树变平衡(Balance a Binary Search Tree)</a>
 * <p>给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。如果有多种构造方法，请你返回任意一种。</p>
 * <p>如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是 平衡的 。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [1,null,2,null,3,null,4,null,null]
 *      输出：[2,1,3,null,null,null,4]
 *      解释：这不是唯一的正确答案，[3,1,4,null,2,null,null] 也是一个可行的构造方案。
 *
 * 示例 2：
 *      输入: root = [2,1,3]
 *      输出: [2,1,3]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树节点的数目在 [1, 10^4] 范围内。</li>
 *     <li>1 <= Node.val <= 10^5</li>* </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/30 16:28
 */
public class LC1382BalanceBinarySearchTree_M {

    static class Solution {
        public TreeNode balanceBST(TreeNode root) {
            if (root == null) {
                return null;
            }
            // 二叉搜索树中序遍历结果是有序的
            List<Integer> preorderResList = new ArrayList<>();
            inorderTraversal(root, preorderResList);
            // 将有序数组转换成平衡的二叉搜索树
            return buildTree(0, preorderResList.size() - 1, preorderResList);
        }

        private TreeNode buildTree(int left, int right, List<Integer> preorderResList) {
            if (left > right) {
                return null;
            }
            // 找到链表的中点
            int mid = left + ((right - left) >> 1);
            TreeNode root = new TreeNode(preorderResList.get(mid));
            root.left = buildTree(left, mid - 1, preorderResList);
            root.right = buildTree(mid + 1, right, preorderResList);
            return root;
        }

        private void inorderTraversal(TreeNode node, List<Integer> resList) {
            if (node == null) {
                return;
            }
            inorderTraversal(node.left, resList);
            resList.add(node.val);
            inorderTraversal(node.right, resList);
        }
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(1);
        root1.right = new TreeNode(2);
        root1.right.right = new TreeNode(3);
        root1.right.right.right = new TreeNode(4);
        Solution solution = new Solution();
        TreeNode.printTree(solution.balanceBST(root1));

        TreeNode root2 = new TreeNode(2);
        root2.left = new TreeNode(1);
        root2.right = new TreeNode(3);
        TreeNode.printTree(solution.balanceBST(root2));
    }
}
